package leetcode.code1728;

public class Solution4 extends Solution1728 {
	int rows;
	int cols;
	int[][] grids;

	int ROAD = 1, WALL = 0, CAT = 2, MOUSE = 3, FOOD = 4;
	int jumpCat;
	int jumpMouse;
	int XFOOD;
	int YFOOD;

	boolean WINMOUSE = true;
	boolean WINCAT = false;
//	boolean[][][][] been;
	Boolean[][][][][] winner;
	boolean[][][] m2, c2;
	int times;

	@Override
	public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
		this.jumpCat = catJump;
		this.jumpMouse = mouseJump;
		rows = grid.length;
		cols = grid[0].length();
		grids = new int[rows][cols];
		int xmouse = 0, ymouse = 0;
		int xcat = 0, ycat = 0;
		for (int i = 0; i < rows; i++) {
			char[] g = grid[i].toCharArray();
			for (int j = 0; j < cols; j++) {
				char c = g[j];
				if (c == '.') {
					grids[i][j] = ROAD;
				} else if (c == '#') {
					grids[i][j] = WALL;
				} else if (c == 'C') {
					grids[i][j] = CAT;
					xcat = i;
					ycat = j;
				} else if (c == 'M') {
					grids[i][j] = MOUSE;
					xmouse = i;
					ymouse = j;
				} else if (c == 'F') {
					grids[i][j] = FOOD;
					this.XFOOD = i;
					this.YFOOD = j;
				}
			}
		}
		times = 1000;
		times = times << 1;
		c2 = new boolean[rows][cols][times + 1];
		m2 = new boolean[rows][cols][times + 1];
		c2[xcat][ycat][0] = true;
		m2[xmouse][ymouse][0] = true;
		winner = new Boolean[rows][cols][rows][cols][times + 1];
//		H.printObject(grids);
		boolean ans = this.mouseMove(0, xmouse, ymouse, xcat, ycat);
		return ans;
	}

	private boolean mouseMove(int round, int xmouse, int ymouse, int xcat, int ycat) {
		if (winner[xmouse][ymouse][xcat][ycat][round] != null) {
//			System.out.println("mouseMove" + winner[xmouse][ymouse][xcat][ycat][round]);
			return winner[xmouse][ymouse][xcat][ycat][round];
		}
		if ((xmouse == xcat && ymouse == ycat) || (round >= times)) {
			winner[xmouse][ymouse][xcat][ycat][round] = false;
//			System.out.println("鼠超时输");
			return false;
		}
		if (XFOOD == xcat && YFOOD == ycat) {
			winner[xmouse][ymouse][xcat][ycat][round] = false;
//			System.out.println("猫抵达，鼠输");
			return false;
		}
		if (XFOOD == xmouse && YFOOD == ymouse) {
			winner[xmouse][ymouse][xcat][ycat][round] = true;
//			System.out.println("鼠抵达，鼠赢");
			return true;
		}
		boolean ans = false;
		// 向上
		for (int i = 0; i <= this.jumpMouse; i++) {
			if (xmouse - i >= 0) {
				if (this.grids[xmouse - i][ymouse] == WALL) {
					break;
				}
				if (!m2[xmouse - i][ymouse][round]) {
//					print("鼠", xmouse, ymouse, "上", i);
					m2[xmouse - i][ymouse][round] = true;
					ans = this.catMove(round + 1, xmouse - i, ymouse, xcat, ycat);
					m2[xmouse - i][ymouse][round] = false;
					if (!ans) {
						winner[xmouse][ymouse][xcat][ycat][round] = true;
						return true;
					}
				}
			} else {
				break;
			}
		}
		// 向下
		for (int i = 0; i <= this.jumpMouse; i++) {
			if (xmouse + i < this.rows) {
				if (this.grids[xmouse + i][ymouse] == WALL) {
					break;
				}
				if (!m2[xmouse + i][ymouse][round]) {
//					print("鼠", xmouse, ymouse, "下", i);
					m2[xmouse + i][ymouse][round] = true;
					ans = this.catMove(round + 1, xmouse + i, ymouse, xcat, ycat);
					m2[xmouse + i][ymouse][round] = false;
					if (!ans) {
						winner[xmouse][ymouse][xcat][ycat][round] = true;
						return true;
					}
				}
			} else {
				break;
			}
		}
		// 向左
		for (int i = 0; i <= this.jumpMouse; i++) {
			if (ymouse - i >= 0) {
				if (this.grids[xmouse][ymouse - i] == WALL) {
					break;
				}
				if (!m2[xmouse][ymouse - i][round]) {
//					print("鼠", xmouse, ymouse, "左", i);
					m2[xmouse][ymouse - i][round] = true;
					ans = this.catMove(round + 1, xmouse, ymouse - i, xcat, ycat);
					m2[xmouse][ymouse - i][round] = false;
					if (!ans) {
						winner[xmouse][ymouse][xcat][ycat][round] = true;
						return true;
					}
				}
			} else {
				break;
			}
		}
		// 向右
		for (int i = 0; i <= this.jumpMouse; i++) {
			if (ymouse + i < this.cols) {
				if (this.grids[xmouse][ymouse + i] == WALL) {
					break;
				}
				if (!m2[xmouse][ymouse + i][round]) {
//					print("鼠", xmouse, ymouse, "右", i);
					m2[xmouse][ymouse + i][round] = true;
					ans = this.catMove(round + 1, xmouse, ymouse + i, xcat, ycat);
					m2[xmouse][ymouse + i][round] = false;
					if (!ans) {
						winner[xmouse][ymouse][xcat][ycat][round] = true;
						return true;
					}
				}
			} else {
				break;
			}
		}
		winner[xmouse][ymouse][xcat][ycat][round] = false;
//		System.out.println("mouseMove" + winner[xmouse][ymouse][xcat][ycat][round]);
		return false;
	}

//	private void print(String string, int xmouse, int ymouse, String string2, int i) {
//		System.out.println(string + " " + xmouse + " " + ymouse + " " + string2 + " " + i);
//
//	}

	private boolean catMove(int round, int xmouse, int ymouse, int xcat, int ycat) {
		if (winner[xmouse][ymouse][xcat][ycat][round] != null) {
//			System.out.println("catMove" + winner[xmouse][ymouse][xcat][ycat][round]);
			return winner[xmouse][ymouse][xcat][ycat][round];
		}
		if ((xmouse == xcat && ymouse == ycat) || (XFOOD == xcat && YFOOD == ycat)) {
			winner[xmouse][ymouse][xcat][ycat][round] = true;
//			System.out.println("猫抵达，猫赢");
			return true;
		}
		if (XFOOD == xmouse && YFOOD == ymouse) {
			winner[xmouse][ymouse][xcat][ycat][round] = false;
//			System.out.println("鼠抵达，鼠赢");
			return false;
		}
		if (round >= times) {
			winner[xmouse][ymouse][xcat][ycat][round] = true;
//			System.out.println("鼠超时输，猫赢");
			return true;
		}
		boolean ans = false;
		// 向上
		for (int i = 0; i <= this.jumpCat; i++) {
			if (xcat - i >= 0) {
				if (this.grids[xcat - i][ycat] == WALL) {
					break;
				}
				if (!c2[xcat - i][ycat][round]) {
//					print("猫", xcat, ycat, "上", i);
					c2[xcat - i][ycat][round] = true;
					ans = this.mouseMove(round + 1, xmouse, ymouse, xcat - i, ycat);
					c2[xcat - i][ycat][round] = false;
					if (!ans) {
						winner[xmouse][ymouse][xcat][ycat][round] = true;
						return true;
					}
				}
			} else {
				break;
			}
		}
		// 向下
		for (int i = 0; i <= this.jumpCat; i++) {
			if (xcat + i < this.rows) {
				if (this.grids[xcat + i][ycat] == WALL) {
					break;
				}
				if (!c2[xcat + i][ycat][round]) {
//					print("猫", xcat, ycat, "下", i);
					c2[xcat + i][ycat][round] = true;
					ans = this.mouseMove(round + 1, xmouse, ymouse, xcat + i, ycat);
					c2[xcat + i][ycat][round] = false;
					if (!ans) {
						winner[xmouse][ymouse][xcat][ycat][round] = true;
						return true;
					}
				}
			} else {
				break;
			}
		}
		// 向左
		for (int i = 0; i <= this.jumpCat; i++) {
			if (ycat - i >= 0) {
				if (this.grids[xcat][ycat - i] == WALL) {
					break;
				}
				if (!c2[xcat][ycat - i][round]) {
//					print("猫", xcat, ycat, "左", i);
					c2[xcat][ycat - i][round] = true;
					ans = this.mouseMove(round + 1, xmouse, ymouse, xcat, ycat - i);
					c2[xcat][ycat - i][round] = false;
					if (!ans) {
						winner[xmouse][ymouse][xcat][ycat][round] = true;
						return true;
					}
				}
			} else {
				break;
			}
		}
		// 向右
		for (int i = 0; i <= this.jumpCat; i++) {
			if (ycat + i < this.cols) {
				if (this.grids[xcat][ycat + i] == WALL) {
					break;
				}
				if (!c2[xcat][ycat + i][round]) {
//					print("猫", xcat, ycat, "右", i);
					c2[xcat][ycat + i][round] = true;
					ans = this.mouseMove(round + 1, xmouse, ymouse, xcat, ycat + i);
					c2[xcat][ycat + i][round] = false;
					if (!ans) {
						winner[xmouse][ymouse][xcat][ycat][round] = true;
						return true;
					}
				}
			} else {
				break;
			}
		}
		winner[xmouse][ymouse][xcat][ycat][round] = false;
//		System.out.println("catMove" + winner[xmouse][ymouse][xcat][ycat][round]);
		return false;
	}

	public static void main(String[] args) {
		Solution4 so = new Solution4();
		so.debug11();
		so.debug10();
		so.debug7();
		so.debug9();
		so.debug8();
		so.debug6();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();

	}

}
